package algorithm.easy;

import pojo.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。
 * <p>
 * 例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。
 * 对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。
 * <p>
 * 返回这些数字之和。题目数据保证答案是一个 32 位 整数。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/sum-of-root-to-leaf-binary-numbers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class SumRootToLeaf1022 {
    List<String> list;

    public int sumRootToLeaf(TreeNode root) {
        list = new ArrayList<String>();
        midIndex(root, "");
        int res = 0;
        for (String s : list) {
            System.out.println(s);
            int i = Integer.parseInt(s, 2);
            res += i;
        }
        return res;
    }

    public void midIndex(TreeNode head, String str) {
        String res = str + head.val;
        if (head.left != null) {
            midIndex(head.left, res);
        }
        if (head.right != null) {
            midIndex(head.right, res);
        }
        if (head.left == null && head.right == null){
            list.add(res);
        }
    }

    // 位运算
    int dfs(TreeNode root, int cur) {
        int ans = 0, ncur = (cur << 1) + root.val;
        if (root.left != null) ans += dfs(root.left, ncur);
        if (root.right != null) ans += dfs(root.right, ncur);
        return root.left == null && root.right == null ? ncur : ans;
    }


}
